// #define print(...)
#define map_t unordered_map
class TimeMap {
// <key, [<timestamp, value>]>
map_t<string, vector<std::pair<int, string>>> tk;

public:
/** Initialize your data structure here. */
TimeMap() {}

void set(string key, string value, int timestamp) {
    tk[key].emplace_back(timestamp, value);
}

string get(string key, int timestamp) {
    if(0 == tk.count(key)) return "";
    auto & values = tk[key];
    auto it = upper_bound(values.begin(), values.end(), pair<int,string>(timestamp,{'z'+1}));
    if(it != values.begin())
        return (it-1)->second;
    return "";
}
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */
